# -*- coding: utf-8 -*-

import os, sys
import math
from random import randint
from collections import deque
import time

import pygame


def notify(text):
    command = """
    terminal-notifier -title 'Maze Notification' -message '%s'
    """ % text
    os.system(command)


class Maze(object):
    """
    """
    screen = None
    def __init__(self, x, y, max_width, max_height, screen, wall, road):
        Maze.screen = screen
        self.wall = wall
        self.road = road

        self.__max_width = max_width    # 包括边界在内
        self.__max_height = max_height

        self.__x = x    # 迷宫的左上角的坐标
        self.__y = y

        self.__real_x = 0   # 除去边界迷宫真正的左上角的x坐标
        self.__real_y = 0

        self.__maze_info = {}     # 包括迷宫的大小，迷宫墙的总行数和总列数
        self.is_generating = False
        self.is_hacking = False

        self.init_data()

    def init_data(self):

        Person.persons.clear()

        self.is_collect_point = True

        self.persons = []

        self.__calculate_rational_size()
        self.__show_maze_border()
        self.__show_maze_initial_wall()
        
        self.show_persons()

    def show_persons(self):
        total_walls_h, total_walls_v = self.get_walls_num()
        wall_width = self.wall.get_vertical_width()
        road_width = self.road.get_width()
        road_height = road_width

        for i in range(0, total_walls_h - 1):
            topleft_x = i * (road_width + wall_width) + wall_width
                                   
            for j in range(0, total_walls_v - 1):
                topleft_y = j * (wall_width + road_height) + wall_width
                pos = (topleft_x, topleft_y)
                real_pos = self.get_real_pos(pos)
                rect = pygame.Rect(real_pos, self.road.get_size())
                person = Person(rect, (i, j))

                # person.show_text(Maze.screen)
                
                # 初始化 ** 列表
                self.persons.append(person)
                self.set_person_neighbors(person)

    def set_person_neighbors(self, person, des=0):
        """
        """
        max_pid_ = self.get_walls_num()
        max_pid = (max_pid_[0] - 2, max_pid_[1] - 2)
        
        neighbor_ids = []

        if not person.pid[0] <= 0:     # 左邻居
            left_pid = (person.pid[0] - 1, person.pid[1])
            neighbor_ids.append(left_pid)

        if not person.pid[0] >= max_pid[0]:   # 右邻居
            right_pid = (person.pid[0] + 1, person.pid[1])
            neighbor_ids.append(right_pid)

        if not person.pid[1] <= 0:
            top_pid = (person.pid[0] , person.pid[1] - 1)
            neighbor_ids.append(top_pid)

        if not person.pid[1] >= max_pid[1]:
            bottom_pid = (person.pid[0], person.pid[1] + 1)
            neighbor_ids.append(bottom_pid)

        person.neighbor_pids = neighbor_ids

    def get_real_pos(self, pos):
        return self.__real_x + pos[0], self.__real_y + pos[1]

    def get_size(self):
        return self.__maze_info['width'], self.__maze_info['height']

    def get_walls_num(self):
        return self.__maze_info['total_walls_h'], self.__maze_info['total_walls_v']

    def on_collect_points_finished(self):
        self.is_collect_point = False

    def draw_horizontal_wall(self, x, y, width=None, height=None):
        """
        由于迷宫的左上角的点已经不再（0，0）的位置，所以重新创建一个函数
        """
        # pythonic
        draw_width = self.wall.get_width() if width is None else width
        draw_height = self.wall.get_height() if height is None else height

        self.wall.draw(self.__real_x + x, self.__real_y + y, draw_width,
                       draw_height)

    def draw_vertical_wall(self, x, y, width=None, height=None):
        draw_width = self.wall.get_width() if width is None else width
        draw_height = self.wall.get_height() if height is None else height

        self.wall.draw(self.__real_x + x, self.__real_y + y, draw_width, draw_height)

    def draw_road(self, x, y, width=None, height=None):
        draw_width = self.wall.get_width() if width is None else width
        draw_height = self.wall.get_height() if height is None else height
        if draw_width != draw_height:
            print u"警告: road 的宽度和高度不相等"
        self.road.draw(self.__real_x + x, self.__real_y + y, draw_width, draw_height)

    def __show_maze_initial_wall(self):
        """初始化 迷宫的墙
        """
        # 算间隔的时候注意，每扇墙都有重叠的部分
        total_walls_h, total_walls_v = self.get_walls_num()

        # 这里为了简便，直接用长条的墙画
        # 画竖直的墙壁

        wall_width = self.wall.get_vertical_width()

        for i in range(0, total_walls_h):
            left_up_point_x = i * (self.road.width +
                                   self.wall.get_vertical_width())

            maze_height = self.get_size()[1]
            self.draw_vertical_wall(left_up_point_x, 0, wall_width,
                                    maze_height)

        # 画水平的墙壁
        for j in range(0, total_walls_v):
            left_up_point_y = j * (self.wall.get_horizontal_height() +
                                   self.road.height)
            maze_width = self.get_size()[0]
            self.draw_horizontal_wall(0, left_up_point_y, maze_width,
                                      wall_width)

    def __show_maze_border(self):
        """
        显示迷宫的边界, 并且更新迷宫真正的左上角的坐标
        """

        width, height = self.get_size()

        border_color = pygame.Color('#0099CC')
        self.wall.change_color(border_color)

        # 计算并画出上边界
        top_space_height = math.ceil((self.__max_height - height) / 2)
        self.wall.draw(self.__x, 0, self.__max_width, top_space_height)

        # 计算并画出下边界
        bottom_space_height = round((self.__max_height - height) / 2)
        bottom_space_y = self.__max_height - bottom_space_height
        self.wall.draw(self.__x, bottom_space_y, self.__max_width, bottom_space_height)

        # 计算并画出左边界
        left_space_width = math.ceil((self.__max_width - width) / 2)
        right_space_width = round((self.__max_width - width) / 2)
        self.wall.draw(self.__x, 0, left_space_width, self.__max_height)

        # ...
        right_space_x = self.__max_width - right_space_width
        self.wall.draw(right_space_x + self.__x, 0, right_space_width, self.__max_height)

        # 更新 迷宫的左上角点的坐标
        self.__real_x = self.__x + left_space_width
        self.__real_y = self.__y + top_space_height

        self.wall.set_default_color()

    def __calculate_rational_size(self):
        """
        根据给定的最大迷宫宽度和高度计算一个合适大小的迷宫

        注意：迷宫初始化的时候所有的墙都在。这涉及到迷宫的形状问题，影响后面的各种计算
        """
        road_width, road_height = self.road.get_size()
        wall_width, wall_height = self.wall.get_size()

        # print u"路的宽度: %d, 路的高度: %d" % (road_width, road_height)

        rational_width = 0
        rational_height = 0

        total_walls_h = 2   # 水平方向墙壁的总数目

        # 计算合理的迷宫宽度
        while True:
            total_roads_h = total_walls_h - 1   # 水平方向上，道路的数目比墙壁的数目少 1

            # 水平总宽度
            total_width = total_roads_h * road_width + total_walls_h * wall_width
            if total_width >= self.__max_width:
                total_walls_h -= 1
                total_roads_h = total_walls_h - 1
                rational_width = total_roads_h * road_width + \
                                 total_walls_h * wall_width
                break
            total_walls_h += 1

        total_walls_v = 2

        # 计算合理的迷宫高度
        while True:
            total_roads_v = total_walls_v - 1

            # 竖直墙壁的高度使用强的宽度来代替计算
            total_height = total_roads_v * road_height + total_walls_h * wall_width
            if total_height >= self.__max_height:
                total_walls_v -= 1
                total_roads_v = total_walls_v - 1
                rational_height = total_roads_v * road_height + \
                                  total_walls_v * wall_width
                break
            total_walls_v += 1

        self.__maze_info['width'] = rational_width
        self.__maze_info['height'] = rational_height
        self.__maze_info['total_walls_h'] = total_walls_h
        self.__maze_info['total_walls_v'] = total_walls_v

        print u"迷宫真正的大小：（%d, %d）" % (rational_width, rational_height)
        print u"迷宫水平的墙壁数目: %d, 迷宫垂直的墙壁数目: %d）" % (total_walls_h, total_walls_v)

        return rational_width, rational_height, total_walls_h, total_walls_v
    
    @classmethod
    def has_wall_between(cls, person_1, person_2):
        """
        判断两条路（块）之间是否存在墙
        实现方法：通过判断颜色是否为白色
        """
        person_1_center = person_1.rect.center
        person_2_center = person_2.rect.center
        
        center_x = ((person_1_center[0] + person_2_center[0]) / 2)
        center_y = ((person_1_center[1] + person_2_center[1]) / 2)

        center_x = int(center_x)
        center_y = int(center_y)

        color = cls.screen.get_at((center_x, center_y))
        if color.normalize() == pygame.Color('#FFFFFF').normalize():
            return False
        # pygame.draw.rect(cls.screen, pygame.Color('red'), (center_x-1,
        #     center_y-1, 2, 2))
        return True

    @classmethod
    def crash_wall(cls, person_1, person_2, color=pygame.Color('#FFFFFF')):
        """打破两条路之间的墙
        
        实现方法：用路的颜色覆盖强的颜色
        """
        if type(person_1) == tuple:
            person_1 = Person.get_person_by_pid(person_1)
            person_2 = Person.get_person_by_pid(person_2)

        left_or_top = person_2
        right_or_bottom = person_1
        # 判断谁在 左方或者上方
        if (left_or_top.rect.x > right_or_bottom.rect.x) or \
                (left_or_top.rect.y > right_or_bottom.rect.y):
            left_or_top, right_or_bottom = right_or_bottom, left_or_top

        topleft = left_or_top.rect.topleft
        bottomright = right_or_bottom.rect.bottomright
        w = bottomright[0] - topleft[0]
        h = bottomright[1] - topleft[1]
        rect = pygame.Rect(topleft, (w, h))
        pygame.draw.rect(cls.screen, color, rect)

    ########################################################
    # A star 走迷宫的算法部分
    ########################################################

    def hack_maze_by_using_astar(self, start_point=None, end_point=None):
        # self.generate_maze_by_using_dfs()

        if self.is_hacking == True:
            command = "Hacking by using astar, please wait..."
            notify(command)
            return

        for person in Person.persons.values():
            person.set_connected(self.screen)
            person.is_walked = False

        self.is_hacking = True
        self.astar_walked_queue = deque()
        self.astar_came_from = []  # 记录astar解法的最终路径

        # 随机生成一个起点
        total_walls_h, total_walls_v = self.get_walls_num()
        start_x = randint(0, total_walls_h - 2)
        start_y = randint(0, total_walls_v - 2)
        start_pid = (start_x, start_y)
        # start_pid = (0, 0)

        start_person = Person.get_person_by_pid(start_pid)
        start_person.set_seed(self.screen)

        end_x = randint(0, total_walls_h - 2)
        end_y = randint(0, total_walls_v - 2)
        end_pid = (end_x, end_y)
        # end_pid = (0, 5)

        end_person = Person.get_person_by_pid(end_pid)
        end_person.set_seed(self.screen)
        pygame.display.update()
        time.sleep(1)
        
        start_person.astar_distance = 0
        self.astar_walked_queue.append(start_person)
        if self.hacking_astar(end_person) == True:
            Maze.draw_astar_path(start_person, end_person)

        self.is_hacking = False
        return True

    @classmethod
    def draw_astar_path(cls, start_person, goal_person):
        start_person.set_seed(cls.screen)
        goal_person.set_seed(cls.screen)
        pygame.display.update()
        time.sleep(1)

        astar_path = list()
        while goal_person.astar_came_from.pid != start_person.pid:
            tmp_person = goal_person.astar_came_from
            astar_path.append(tmp_person)
            goal_person = tmp_person

        astar_path.reverse()
        tmp_person = astar_path[0]
        for person in astar_path:
            Maze.crash_wall(tmp_person, person, pygame.Color('#FF6666'))
            pygame.display.update()
            tmp_person = person
        return

    @classmethod
    def astar_heuristic(cls, current_person, goal_person, flag=True):
        dis_x = abs(current_person.pid[0] - goal_person.pid[0])
        dis_y = abs(current_person.pid[1] - goal_person.pid[1])
        return dis_x + dis_y

    def hacking_astar(self, goal_person):
        while len(self.astar_walked_queue) > 0:
            # 因为后面的顺序是从大到小
            current_person = self.astar_walked_queue.popleft()
            print "排序之后选择了：", current_person.calculate_total_distance(goal_person)

            current_person.set_tried(self.screen)
            pygame.display.update()

            if current_person.pid == goal_person.pid:
                notify("Hacking succeed !")
                return True

            current_dis = current_person.astar_distance
            for neighbor_pid in current_person.neighbor_pids:
                neighbor = Person.get_person_by_pid(neighbor_pid)

                if not Maze.has_wall_between(current_person, neighbor):
                    if neighbor.astar_distance == None:
                        neighbor.astar_distance = 1 + current_dis   # 1 如果不同的话，就是不同权重
                        neighbor.astar_came_from = current_person
                        self.astar_walked_queue.append(neighbor)
                    else:
                        neighbor.astar_distance = neighbor.astar_distance 

                        # 在这里没有判断相等的情况
                        # 相等的话说明可以有两条道路走，这里就不做考虑了。
                        if not (1 + current_dis) > neighbor.astar_distance:
                            neighbor.astar_distance = 1 + current_dis
                            neighbor.astar_came_from = current_person
       
            print "排序中... "
            tmp_list = list()   # 在这中迷宫中，queue中最多四个元素
            while len(self.astar_walked_queue) > 0:
                tmp_person = self.astar_walked_queue.pop()
                tmp_dis = tmp_person.calculate_total_distance(goal_person)
                
                if len(tmp_list) > 0:
                    last_person = tmp_list[-1]
                    if tmp_person.calculate_total_distance(goal_person) >= \
                            last_person.calculate_total_distance(goal_person):
                        tmp_list.append(tmp_person)
                        continue

                    for i, person in enumerate(tmp_list):
                        if tmp_dis < person.calculate_total_distance(goal_person):
                            tmp_list.insert(i, tmp_person)
                            break
                else:
                    tmp_list.append(tmp_person)
            
            for person in tmp_list:
                print person.calculate_total_distance(goal_person)
            
            self.astar_walked_queue = deque(tmp_list)
            # sorted(self.astar_walked_queue, key=lambda person:
            #         person.calculate_total_distance(goal_person))

            print "排序完毕... "

        notify('Hacking failed !')
        return False
    
    ########################################################
    # dfs 走迷宫的算法部分
    ########################################################

    def hack_maze_by_using_dfs(self, start_point=None, end_point=None):
        if self.is_hacking == True:
            command = "Hacking, please wait..."
            notify(command)
            return

        for person in Person.persons.values():
            person.set_connected(self.screen)
            person.is_walked = False

        self.is_hacking = True
        self.walked_stack = []
        self.walked_persons = []
        self.dfs_maze_path = []  # 记录dfs解法的最终路径

        # 随机生成一个起点
        total_walls_h, total_walls_v = self.get_walls_num()
        start_x = randint(0, total_walls_h - 2)
        start_y = randint(0, total_walls_v - 2)
        start_pid = (start_x, start_y)
        # start_pid = (0, 0)

        start_person = Person.get_person_by_pid(start_pid)
        start_person.set_seed(self.screen)

        end_x = randint(0, total_walls_h - 2)
        end_y = randint(0, total_walls_v - 2)
        end_pid = (end_x, end_y)
        # end_pid = (0, 5)

        end_person = Person.get_person_by_pid(end_pid)
        end_person.set_seed(self.screen)
        pygame.display.update()
        time.sleep(1)

        self.hacking_dfs(start_person, end_person)
        self.draw_dfs_maze_path()

        self.is_hacking = False
        return True

    def draw_dfs_maze_path(self):
        tmp_person = self.dfs_maze_path[0]
        for person in self.dfs_maze_path:
            Maze.crash_wall(tmp_person, person, pygame.Color('#FF6666'))
            tmp_person = person
            pygame.display.update()

    def hacking_dfs(self, current_person, goal_person):
        self.dfs_maze_path.append(current_person)

        current_person.is_walked = True
        current_person.set_tried(self.screen)
        # pygame.display.update()

        # print "walked person: %d, walked stack: %d" % (len(self.walked_persons),
        #         len(self.walked_persons))
        neighbor_pid = current_person.get_walkable_neighbor_pid(current_person)
        # print "walking: ", neighbor_pid

        if current_person.pid == goal_person.pid:
            notify('hacking succeed !')
            return True

        if neighbor_pid == False:
            if len(self.walked_stack) > 0:
                self.dfs_maze_path = list(self.walked_stack)
                
                current_person = self.walked_stack.pop()
                return self.hacking_dfs(current_person, goal_person)

            notify('hacking failed !')
            return False
        
        neighbor = Person.get_person_by_pid(neighbor_pid)

        self.walked_stack.append(current_person)
        self.walked_persons.append(current_person)

        current_person = neighbor
        return self.hacking_dfs(neighbor, goal_person)

        

    ########################################################
    # dfs 生成迷宫的算法部分
    ########################################################
        
    def generate_maze_by_using_dfs(self, point=None):
        """dfs 生成迷宫的入口部分
        """
        if self.is_generating == True:  # 判断现在是不是正在生成迷宫
            command = "a maze is generating, please wait..."
            notify(command)
            return

        command = "generating maze by using dfs algorithm"
        notify(command)     # 对现在的状态进行通知
        self.is_generating = True   # 把现在的状态改为正在生成迷宫

        self.init_data()

        # 下面是主要的算法部分, person代表迷宫中的路
        self.unconnected_persons = self.persons     # 保存很多person的对象
        self.connected_persons = []
        self.visited_stack = list()
        
        # 随机生成一个起始点
        total_walls_h, total_walls_v = self.get_walls_num()
        seed_x = randint(0, total_walls_h - 2)
        seed_y = randint(0, total_walls_v - 2)
        seed_pid = (seed_x, seed_y)
        seed_person = Person.get_person_by_pid(seed_pid)
        seed_person.set_seed(self.screen)
        pygame.display.update() 
        time.sleep(1)
        
        self.generate_dfs(seed_person)
        self.is_generating = False
        return True

    def generate_dfs(self, current_person):
        """dfs 生成迷宫核心算法
        """
        self.connected_persons.append(current_person)
        self.unconnected_persons.remove(current_person)
        current_person.is_connected = True

        while len(self.unconnected_persons) > 0:    # 当还有未被访问的点
            self.mark_neighbor_to_no(current_person)
            while len(self.visited_stack) > 0:
                current_person = self.visited_stack.pop()
                self.mark_neighbor_to_no(current_person)
            count = len(self.unconnected_persons)
            print u"剩余的没有连接的点个数: %d" % count
            if count == 0:
                break
            num = randint(0, count)
            current_person = self.unconnected_persons[num]
            return self.generate_dfs(current_person)
        return True

    def mark_neighbor_to_no(self, current_person):
        """dfs 生成迷宫的一部分
        
        选择当前点的一个邻居来充当当前点
        """
        neighbor_pid = current_person.get_random_unconnected_neighbor_pid()
        if neighbor_pid != False:
            # 随机选择一个邻格
            neighbor = Person.get_person_by_pid(neighbor_pid)

            # 将当前格入栈
            self.visited_stack.append(current_person)

            # 拆墙
            Maze.crash_wall(current_person, neighbor)   # 把墙销毁
            pygame.display.update()
            
            # 标记已经访问过的点
            self.connected_persons.append(neighbor)
            self.unconnected_persons.remove(neighbor)
            neighbor.is_connected = True    # 标记邻格
            
            # 将邻格设为当前格
            current_person = neighbor
            return self.mark_neighbor_to_no(current_person)
        
        # 当前格已经没有未被标记的邻格了
        return True
    
    
class Person(object):
    """
    """
    
    font = None
    
    persons = {}

    def __init__(self, rect, pid):
        """
        rect: pygame.Rect类型
        pid: 元组，包含 id_x, id_y
        """

        if Person.font is None:
            raise Warning('Person font not initialized')

        self.rect = rect
        self.pid = pid      # 在迷宫中的抽象位置

        self.is_connected = False   # 生成迷宫时候用
        self.is_walked = False  # 破解迷宫时候用

        self.astar_distance = None
        self.astar_came_from = None
        self.neighbor_pids = []

        Person.persons[pid] = self
        
    @classmethod
    def init(cls, font):
        cls.font = font

    def show_text(self, screen, color=pygame.Color('#222222')):
        text = str(self.pid)
        label = Person.font.render(text, True, color)
        font_size = Person.font.size(text)
        h_spacing = (self.rect.w - font_size[0]) / 2
        v_spacing = (self.rect.h - font_size[1]) / 2
        screen.blit(label, (self.rect.x + h_spacing, self.rect.y + v_spacing))

    def hide_text(self, screen, color=pygame.Color('#CCCCCC')):
        pygame.draw.rect(screen, color, self.rect)

    def set_connected(self, screen, color=pygame.Color('#FFFFFF')):
        pygame.draw.rect(screen, color, self.rect)
        self.is_connected = True
    
    def set_seed(self, screen, color=pygame.Color('#FF6666')):
        pygame.draw.rect(screen, color, self.rect)

    def set_tried(self, screen, color=pygame.Color('#CCCCCC')):
        pygame.draw.rect(screen, color, self.rect)

    def get_walkable_neighbor_pid(self, screen):
        count = 0
        unwalked_neighbor_pids = []
        for neighbor_pid in self.neighbor_pids:
            neighbor = Person.get_person_by_pid(neighbor_pid)
            if not Maze.has_wall_between(self, neighbor):
                if neighbor.is_walked == False:
                    count += 1
                    unwalked_neighbor_pids.append(neighbor_pid)
        # print u"我有 %d 个可以走通的邻居" % count
        if count <= 0:
            return False
        target = randint(0, count-1)
        return unwalked_neighbor_pids[target]

    def get_random_unconnected_neighbor_pid(self):
        count = 0
        unconnected_neighbor_pids = []
        for neighbor_pid in self.neighbor_pids:
            neighbor = Person.get_person_by_pid(neighbor_pid)
            if neighbor.is_connected == False:
                count += 1
                unconnected_neighbor_pids.append(neighbor_pid)
        if count <= 0:
            return False
        
        target = randint(0, count-1)
        return unconnected_neighbor_pids[target]

    def get_neighbor_pid(self, des=0):
        """
        des: 代表是哪个邻居，0:left, 1:right, 2:top, 3:bottom
        """
        for neighbor_pid in self.neighbor_pids:
            if des == 0:
                if neighbor_pid[0] == self.pid[0] - 1:
                    return neighbor_pid
            elif des == 1:
                if neighbor_pid[0] == self.pid[0] + 1:
                    return neighbor_pid
            elif des == 2:
                if neighbor_pid[1] == self.pid[1] - 1:
                    return neighbor_pid
            elif des == 1:
                if neighbor_pid[1] == self.pid[1] + 1:
                    return neighbor_pid
        return None

    def get_left_neighbor_pid(self):
        return self.get_neighbor_pid(0)

    def get_right_neighbor_pid(self):
        return self.get_neighbor_pid(1)

    def get_top_neighbor_pid(self):
        return self.get_neighbor_pid(2)

    def get_bottom_neighbor_pid(self):
        return self.get_neighbor_pid(3)

    def calculate_total_distance(self, goal_person):
        """给A*算法用
        """
        dis = Maze.astar_heuristic(self, goal_person) + self.astar_distance
        
        # 这一部分不应该写的这么水的
        btn = Person.font.render(str(dis), True, pygame.Color('#222222'))
        font_size = Person.font.size(str(dis))
        h_spacing = (self.rect.w - font_size[0]) / 2
        v_spacing = (self.rect.h - font_size[1]) / 2
        Maze.screen.blit(btn, (self.rect.x + h_spacing, self.rect.y + v_spacing))

        # print 'pid: ', self.pid, ' dis: ', dis
        return dis
                
    @classmethod
    def get_person_by_pid(cls, pid):
        return cls.persons[pid]
        btn = self.font.render(str(dis), True, color)
